package leetcode;

import java.util.Arrays;

//Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), 
//prove that at least one duplicate number must exist. 
//Assume that there is only one duplicate number, find the duplicate one.

//There is only one duplicate number in the array, but it could be repeated more than once.

public class DuplicateNumber {

	public static void main(String[] args) {
		int[] nums = {1, 1};
		DuplicateNumber num = new DuplicateNumber();
		System.out.println(num.findDuplicate2(nums));
	}
	// the first solution is sort and find, the time complexity is O(nlogn)
	// However, it change the Array, It's bad idea
	// and I think there are O(n) time complexity
	public int findDuplicate(int[] nums) {
		if (nums == null || nums.length <= 0) {
			return 0;
		}
		Arrays.sort(nums);
		for (int i = 0; i < nums.length - 1; i++) {
			if (nums[i] == nums[i + 1]) {
				return nums[i];
			}
		}
		return -1;
	}
	
	//cycle detection
//	假设数组中没有重复，那我们可以做到这么一点，就是将数组的下标和1到n每一个数一对一的映射起来。
//	比如数组是213,则映射关系为0->2, 1->1, 2->3。假设这个一对一映射关系是一个函数f(n)，其中n是下标，f(n)是映射到的数。
//	如果我们从下标为0出发，根据这个函数计算出一个值，以这个值为新的下标，再用这个函数计算，以此类推，直到下标超界。
//	实际上可以产生一个类似链表一样的序列。比如在这个例子中有两个下标的序列，0->2->3。

//  但如果有重复的话，这中间就会产生多对一的映射，比如数组2131,则映射关系为0->2, {1，3}->1, 2->3。
//	这样，我们推演的序列就一定会有环路了，这里下标的序列是0->2->3->1->1->1->1->...，而环的起点就是重复的数。
	
	public int findDuplicate2(int[] nums) {
		if (nums == null || nums.length <= 0) {
			return 0;
		}
		int slow = 0;
		int fast = 0;
		//由于这个有重复数字，所以一定会出现环
		//刚开始我写的是while循环，这样子初始就跳过了
		do{
			slow = nums[slow];  //获取到下标到数字的映射
			fast = nums[nums[fast]];  //fast相当于移动了两步
		}while(slow != fast);
		//此时只是两者相遇了，我们还需要找到环的入口
		int finder = 0;
		while(slow != finder){
			slow = nums[slow];
			finder = nums[finder];
		}
		return finder;
	}
}
